package org.datacoder.geocoding.datastructures.intervals

import org.datacoder.geocoding.*
import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.points.*
import org.datacoder.geocoding.datastructures.rectangles.*
import org.datacoder.geocoding.jurisdiction.*

class LayeredSegmentRangeTree implements IntersectingIntervalsFinder {

    public LayeredSegmentRangeTreeNode root
    public int type

    public LayeredSegmentRangeTree(Collection<Jurisdiction> jurisdictions, int type){
        this.type = type
        SortedSet<Double> endPointSet = new TreeSet<Double>()
        Set<GeoInterval> geoIntervals = new HashSet<GeoInterval>()
        for(juris in jurisdictions){
            GeoInterval gi = juris.toGeoInterval(type)
            geoIntervals.add(gi)
            endPointSet.add(gi.retrieveMinDoubleValue())
            endPointSet.add(gi.retrieveMaxDoubleValue())
        }
        double[] endPoints = new double[endPointSet.size()]
        Iterator iter = endPointSet.iterator()
        for(int i = 0; i < endPoints.length; i++){
            endPoints[i] = iter.next()
        }
        if(endPoints.length == 0){
            root = null
        }else{
            root = createNode(endPoints, 0, endPoints.length)
        }
        for(gi in geoIntervals){
            addGeoInterval(root, gi)
        }
        lock()
    }

    public LayeredSegmentRangeTreeNode createNode(double[] endPoints, int startIndex, int endIndex){
        LayeredSegmentRangeTreeNode lsrtNode = new LayeredSegmentRangeTreeNode(type)
        lsrtNode.leftValue = endPoints[startIndex]
        lsrtNode.rightValue = endPoints[endIndex - 1]
        int middle = (startIndex + endIndex)/2
        if(startIndex < endIndex - 2){
            lsrtNode.left = createNode(endPoints, startIndex, middle + 1)
            lsrtNode.right = createNode(endPoints, middle, endIndex)
        }
        return lsrtNode
    }

    public void addGeoInterval(LayeredSegmentRangeTreeNode lsrtNode, GeoInterval gi){
        if(gi.containsInterval(lsrtNode.leftValue, lsrtNode.rightValue)){
            lsrtNode.addJurisdiction(gi.juris)
        }else{
            if((lsrtNode.left != null) && gi.intersectsInterval(lsrtNode.left.leftValue, lsrtNode.left.rightValue)){
                addGeoInterval(lsrtNode.left, gi)
            }
            if((lsrtNode.right != null) && gi.intersectsInterval(lsrtNode.right.leftValue, lsrtNode.right.rightValue)){
                addGeoInterval(lsrtNode.right, gi)
            }
        }
    }

    public void lock(){
        Queue<LayeredSegmentRangeTreeNode> lsrtNodeQueue = new LinkedList<LayeredSegmentRangeTreeNode>()
        lsrtNodeQueue.offer(root)
        while(lsrtNodeQueue.peek() != null){
            LayeredSegmentRangeTreeNode currentNode = lsrtNodeQueue.poll()
            currentNode.lock()
            if(currentNode.left != null){
                lsrtNodeQueue.offer(currentNode.left)
            }
            if(currentNode.right != null){
                lsrtNodeQueue.offer(currentNode.right)
            }
        }
    }

    public Set<Jurisdiction> findIntersectingIntervals(GeoInterval gi){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        if(!root.containsPoint(gi.retrieveSingleValue())){
            return jurisdictions
        }
        Queue<LayeredSegmentRangeTreeNode> lsrtNodeQueue = new LinkedList<LayeredSegmentRangeTreeNode>()
        lsrtNodeQueue.offer(root)
        while(lsrtNodeQueue.peek() != null){
            LayeredSegmentRangeTreeNode currentNode = lsrtNodeQueue.poll()
            jurisdictions.addAll(currentNode.findPointsWithinInterval(gi.retrieveMinDoubleValue(), gi.retrieveMaxDoubleValue()))
            if((currentNode.left != null) && (currentNode.left.containsPoint(gi.retrieveSingleValue()))){
                lsrtNodeQueue.offer(currentNode.left)
            }
            if((currentNode.right != null) && (currentNode.right.containsPoint(gi.retrieveSingleValue()))){
                lsrtNodeQueue.offer(currentNode.right)
            }
        }
        return jurisdictions
    }

}

